package com.easy;

import java.util.Arrays;

public class KMP {

    public void getNext(int[] next,String pattern){
        //初始化
        int j=0;
        next[0]=0;
        //处理不匹配的情况
        for (int i = 1; i <pattern.length() ; i++) {
            while (j>0&&pattern.charAt(i)!=pattern.charAt(j)){
                j=next[j-1];
            }
            //匹配的情况
            if (pattern.charAt(i)==pattern.charAt(j)){
                j++;
            }
            //填充数组
            next[i]=j;
        }
    }

    public static void main(String[] args) {
        KMP kmp = new KMP();
        String pattern="aabaaf";
        int[] next = new int[pattern.length()];
        kmp.getNext(next,pattern);
        System.out.println(Arrays.toString(next));
    }
}
